1. Field of the Invention:
A machine process in a digital computer operating in accordance with a computer program for routing electrical interconnections between electrical devices and for compacting the channel formed between the electrical devices.
2. Description of Related Art:
Routing interconnections between devices has long time been a design problem, particularly when the interconnections are restrained to a planar field having a limited number of levels. The planar field may be arbitrary in orientation, but will be described hereinafter as horizontal. Frequently the interconnections need to cross paths in a horizontal direction without intersecting. This requires at least one of the interconnections to shift in a vertical direction to avoid intersecting the other interconnection at a crossing point. Thus, at least one interconnection must be in a different level of the planar field so that the interconnections can cross paths without intersecting. FIG. 1 schematically illustrates the effect.
In FIG. 1, three interconnections 11, 12, 13 connect two devices (not shown) separated by a channel. The outer two interconnections 11, 13 exchange locations relative to the devices which requires both of the outer interconnections 11, 13 to cross the straight, central interconnection 12 without intersecting. This could not be accomplished in one level if the interconnections are to remain in the channel formed between the two devices. Therefore, the outer interconnections 11, 13 shift to different levels in order to cross paths. FIG. 1a illustrates a cross-sectional view of the interconnections 11, 12 and 13 shown in FIG. 1.
It should be appreciated that the routing of such interconnections has many applications. These applications include interconnecting electrical devices in a semiconductor chip and interconnecting discreet electrical devices, such as integrated circuit chips, through a layered wiring board. The routing techniques disclosed herein also have application to relatively complex piping systems, such as those found at chemical plants, or any other application where it is useful to route more than one continuous interconnection between objects without intersecting any other interconnection.
For ease of discussion, the following will be principally directed to applying the inventive technique to the routing of lead lines, or wires, between electrical devices formed in a semiconductor device. In such devices, wires are formed by more than one layer of conductive material, such as metalization layers M1, M2, or heavily doped polysilicon P3. Each conductive layer is insulated from the others by interposed insulation layers (not shown).
Each conductive layer is assigned a primary direction in which the wire segments appearing therein travel. For instance, a semiconductor substrate may have formed thereon three layers of conductive material, two of which form wire segments whose axes are perpendicular to the nearest side of the electrical devices. Wire segments are formed in the third layer have axes in a direction parallel to the electrical devices. The wire segments in each layer are connected to other segments through via holes in the insulation layers. In this system, at each instance an interconnection changes direction, or jogs, it must change its level, thereby requiring a via hole. It is desirable to reduce the number of via holes to avoid problems in alignment and reduce the complexity of formation.
Because of the desire to reduce the amount of unused or under-used space, particularly on a semiconductor chip, it is important that the devices being interconnected are as closely adjacent to one another as possible. The process of reducing the space between adjacent devices is called channel compaction. Compacting the channel formed between devices is, however, limited by design rules. Design rules are governed by, for example, spacing tolerances for wires. The design rules are also based on such things as resistance, inductance and capacitance, design and production restraints, material tolerances, etc.
Routing interconnections between devices quickly becomes complex as the number of interconnections increases. This complexity has led to the enlistment of computers. In the field of computer-aided design, a digital computer operating under a stored program routes interconnections between one electrical device and another electrical device on a planar field. In addition, such a digital computer compacts the channel or channels between the devices after they are interconnected or routed.
An example of a prior art technique for routing interconnections between devices and/or the positioning of devices after they have been routed by the use of a digital computer is disclosed in U.S. Pat. No. 3,681,782. This patent discloses a machine process for positioning interconnected components to minimize interconnection line length. Another method is disclosed in Rabbie and Jacobson, "Gridless Channel Routing and Compaction for Cell Based Custom IC Layout," IEEE 1986 Custom Integrated Circuits Conference, page 297, May 12, 1986. Rabbie and Jacobson disclose compacting by moving tracks against a contour of a device in one direction only. The Rabbie and Jacobson method is limited to rectangularly shaped objects that do not have any irregular contours and require even spacing of the interconnection pins. See also, Sangiovanni-Vincentelli et al., "A New Gridless Channel Router II (YACR II)," Prod. International Conference On Computer-Aided Design 84, pages 72-75, 1984; and Ng, "An Industrial World Channel Router for Non-Rectangular Channels," Prod. 23rd Third Design Automation Conference, pages 490-494, 1986. Hereinafter, these methods will be collectively referred to as the YACR method.
An improvement on the Rabbie and Jacobson technique is disclosed in U.S. Pat. No. 4,965,739 to Ng, commonly assigned to the assignee of the present application and incorporated herein by reference. In the Ng patent, a machine process for routing interconnections from one device to another device on a planar field with the aid of a computer is accomplished in two primary steps or passes. The first pass pushes contours of the wires toward one device to minimize the space occupied by each wire, at least in regions where the wires are most densely populated. Once the wires are as closely adjacent as feasible, the channel formed between the two devices is compacted by moving the devices toward one another, thus reducing the amount of space used for interconnecting the devices. A second pass straightens the wires to reduce the number of via holes. In other words, the jogs appearing in the wires are reduced in number.
The Ng patent represents an improvement over the preexisting methods. However, the routing process disclosed in the Ng patent can be improved upon. Using the technique disclosed in the Ng patent, the first pass pushes or shifts all the contours of the wires in one direction but, in some instances, this does not effectively shorten all the wires. For example, wires having starting and ending points on the same electrical device may actually be extended using this technique. This occurs when the starting and ending points appear on the device in a direction opposite to the direction the wires are pushed in the second pass of the Ng technique. The technique disclosed in the Ng patent does not accommodate these wires possibly causing the segments of these wires parallel to the devices to be pushed further from the device of their origin and termination, thus lengthening the wires.
The prior art techniques also do not take into account the cost differences among the various layers. Some layers may be more costly than the others. In this sense, cost may encompass not only the economic cost of forming wires but also the cost of increased resistance, capacitance and inductance formed by and around such wires, the difficulty in forming such wires, the amount of space occupied by such wires, the design restraints imposed thereon, etc. Generally, it is the electrical resistance which plays the most important factor. The net effect of the cost differences is that it is often desirable to minimize the amount of wire segments appearing in the costly conductive layers.
For example, the polysilicon layer P3 may be the most costly layer of three conductive layers, the other two of which may be metals M1 and M2 in a semiconductor structure. Thus, the prior art methods may result in the use of extensive amounts of the most costly conductive layer when a less costly conductive layer is a readily available alternative.